package com.mid;

import java.util.ArrayList;
import java.util.List;

/**
 * Created by Lxk on 2019/7/13.
 */
public class Solution120 {
    public int minimumTotal(List<List<Integer>> triangle) {
        if(triangle.size()==1){
            return triangle.get(0).get(0);
        }else{
            for(int i = 1;i < triangle.size(); i++){
                for(int k = 0;k < triangle.get(i).size(); k++){
                    if(k==0){
                        int val = triangle.get(i).get(0) + triangle.get(i-1).get(0);
                        triangle.get(i).set(0,val);
                    }else if(k==triangle.get(i).size()-1){
                        int val = triangle.get(i).get(triangle.get(i).size()-1) + triangle.get(i-1).get(triangle.get(i-1).size()-1);
                        triangle.get(i).set(triangle.get(i).size()-1,val);
                    }else{
                        int leftVal = triangle.get(i).get(k) + triangle.get(i-1).get(k-1);
                        int rightVal = triangle.get(i).get(k) + triangle.get(i-1).get(k);
                        triangle.get(i).set(k,leftVal>rightVal?rightVal:leftVal);
                    }
                }
            }
        }
        int min = Integer.MAX_VALUE;
        for(int i = 0;i < triangle.get(triangle.size()-1).size(); i++){
            if(triangle.get(triangle.size()-1).get(i)<min){
                min = triangle.get(triangle.size()-1).get(i);
            }
        }
        return min;
    }

    public static void main(String[] args) {
        List<List<Integer>> testData = new ArrayList<>();
        List<Integer> list = new ArrayList<>();
        list.add(2);
        List<Integer> list2 = new ArrayList<>();
        list2.add(3);
        list2.add(4);
        List<Integer> list3 = new ArrayList<>();
        list3.add(6);
        list3.add(5);
        list3.add(7);
        List<Integer> list4 = new ArrayList<>();
        list4.add(4);
        list4.add(1);
        list4.add(8);
        list4.add(3);
        testData.add(list);
        testData.add(list2);
        testData.add(list3);
        testData.add(list4);
        Solution120 solution120 = new Solution120();
        System.out.println(solution120.minimumTotal(testData));
    }
}
